This chapter discusses in detail the array objects included in the Containers Library. It describes how to use the arrays and the different types of arrays available.
In this chapter you will learn:
- What are arrays?
- How to use the arrays
- The characteristics of each type of array
What are arrays?
An array is a finite ordered group of homogeneous elements. The ordered property means that it is possible to identify the first, second, third, . . . , and n element in the array. A dynamic array is an array for which a size can be set at runtime, instead of at compile time, as with standard arrays. The simplest form of an array is the unidimensional array.
Arrays are the most simple of all data structures. Borland/Turbo Pascal compilers already include an array data type, but arrays of this type are limited in two aspects: the size of the arrays must be set at compile time, and they cannot be larger than 64k in size. Arrays in the Containers Library do not have these limitations and provide greater flexibility of use to the programmer.
There are two types of arrays implemented in the library: memory based arrays and stream based arrays. Memory based arrays work very much like Borland arrays: they let you store and retrieve non-dynamically allocated data, although the use of pointers to some extent is required. Standard arrays are faster than other arrays but still have the 64k limit, while huge arrays have no practical memory limit.
Stream arrays offer the greatest flexibility since you can choose where to store the array. You can store the array in conventional memory, in expanded memory or even in a file if you wish to do so. Unlike standard arrays, however, stream arrays require the use of dynamically allocated items.
There is also another type of array that is not static in size: the resizable array. This array gives the programmer a broader range of possibilities from which to choose. Resizable arrays share all the characteristics of collections, but let you work with non-dynamically allocated data. Sorted arrays are resizable arrays that let you sort and search items by key.
Like with normal arrays, when initializing an array container you must define the range of valid indexes for elements in the array and the individual size of those elements. When using the normal array containers, you will always use the AtInsert method instead of the Insert method to add data to the array. This is because normal array containers are static in size. Using Insert will cause the array to attempt to insert the item at the position following the last valid element, producing a "range check" error. When working with resizable arrays, you can use either the Insert or AtInsert methods to insert data into the array.
Memory based arrays
Memory based arrays work very much like Borland arrays: they let you work with data that is not dynamically allocated, in the same you way would work with an array allocated at compile-time. Depending on the size of the array you want to use, you can choose from the standard arrays (which have a 64K size limit but are the fastest) and the huge arrays (which have no practical size limit). In our examples, we will use a TStdArray; however, we could have used a THugeArray instead with no modifications to the code.
Creating a memory based array
As with the collections, to begin using an array you need to create the data type that you wish to store into the array. Suppose we want to keep track of weather information at different hours in the day. Since arrays work with non-dynamically allocated data, we will use a record type to store weather information for each hour:
type
PWeatherInfo = ^TWeatherInfo;
TWeatherInfo = record
Location : string[20];
Humidity : Integer;
Rain : Integer;
end;
Notice that we also declared a pointer to the record type. It is a good idea to always declare a pointer to the data type you are using, since it will facilitate your access to the data. Now we will create and initialize the array that we will use:
var
MorningWeatherData : PStdArray;
WeatherInfo: TWeatherInfo;
begin { arrays1.pas }
{...}
MorningWeatherData := New(PStdArray, Init(7, 11,
SizeOf(TWeatherInfo)));
{...}
Dispose(MorningWeatherData, Done);
end;
When creating an array, you must provide the starting and ending values for elements' indexes, and the size of each element.
Using a memory based array
To insert data into the array, we simply fill an instance of a TWeatherInfo record with the appropriate data, and pass a pointer to it to the AtInsert method of the array:
You could also access the array data directly (see arrays2.pas), though this is not recommended to keep your applications as data-structure independent as possible. For example:
with MorningWeatherData^ do
with PWeatherInfo(At(7))^ do
begin
Location := Miami;
Humidity := 34;
Rain := 0;
end;
Object arrays
Memory based object arrays are used to store non-dynamically allocated objects that are descendants of TObject. Using these arrays is just like using the standard arrays. However, you must be extra careful to always initialize the objects that you insert into the array. Otherwise, the array will see the objects as uninitialized, and therefore, will not call their destructor methods when you dispose of the entire array.
We'll now rewrite our previous weather information example using objects instead of records. In our TWeatherInfo object, we will use fields of type PString so that memory is only allocated for the portion of the string that is actually used.
The last statement will dispose of the entire array and all the objects in it. The array will call each object's Done destructor, but only if the object has been properly initialized. If the array finds an object that has not been initialized, it will not call its Done destructor.
As with the standard arrays, you can also access the data in the array directly (see arrays4.pas). For example,
with MorningWeatherData^ do
with PWeatherInfo(At(7))^ do
Init('Miami', 34, 0);
Again, this is not recommended to keep your applications as data structure independent as possible.
Resizable arrays
Resizable arrays are a combination of the dynamically sizing capabilities of collections, with the ability of storing non-dynamically allocated data of standard arrays.
To show the use of resizable arrays, we'll use the contact list example used previously. To store the data in the array, we'll use the following record structure:
type
TContact = record
FirstName : string[15];
LastName : string[20];
Phone : string[18];
CompanyName : string [25];
end;
Creating a resizable array is like creating a collection: you must indicate the initial size of the array, and then the increments by which the array will grow. To insert items into the array, you simply fill a record instance with the appropriate data and call the array's insert method:
When using resizable arrays, you should always call the Insert method to insert the data into the array. Once the data is stored in the array, you can access it directly just like with a normal compile-time array, but again, this is not recommended.
To store objects instead of records, you must use the resizable object arrays (see arrays6.pas). Remember to call the Init method for each object that you insert into any object array!
Sorted arrays
A sorted array is a special kind of resizable array that will sort items by key. To use a sorted array, you must first override the KeyOf method, to let the array know how you want to sort the data.
type
PSortedContactList = ^TSortedContactList;
TSortedContactList = object(TSortedStdArray)
function KeyOf(Item : Pointer): Pointer; virtual;
end;
function TSortedContactList.KeyOf(Item: Pointer) : Pointer;
begin
KeyOf := @(PContact(Item)^.LastName);
end;
Now, you simply create an instance of the new array and insert items using the Insert method (see arrays7.pas). If you want to store objects instead, you must use the sorted object arrays, which are also included.
Stream arrays
Stream arrays are another type of array that will store the data in a stream, instead of storing it in the heap. However, unlike memory based arrays, stream arrays work only with dynamically allocated data.
Creating a stream array
To create a stream array, you must provide the starting and ending values for the elements' indexes, and the size of each element (just like we did with the memory based standard arrays). In the following examples, we will use the TWeatherInfo record structure used before.
By default, stream arrays use a TMemoryStream to store the data in the array. If you wish to use a different type of stream, you must override the InitStream method. This is what TEmsXXXX arrays do.
Using a stream array
Since stream arrays work with dynamically allocated data, we must allocate each item that we will store in the array. This is done by the SetWeatherValues procedure, which returns a pointer to the newly allocated item:
The DoneItem method plays an important part in the use of stream arrays. To understand better the reason for this, look at the following storage diagram for a stream array:
(see fig7_1.gif)
When items are inserted into the array, all the information is copied to stream. When an item is retrieved, a new copy of the item is allocated in the heap:
(see fig7_2.gif)
If you retrieve the same item again, another copy will be created. Therefore, you must always call DoneItem when done using a data item you retrieve from the stream array. This is true even if you free (delete and dispose of) an item in the array. For example, if you retrieve item 5 and then call AtFree(5), only the item in the stream will be freed; you still have to dispose of the copy that you retrieved. This is also the reason you must allocate every item you insert into an array, since DoneItem will be automatically called for the item immediately after it is inserted into the array.
You must consider the way stream arrays handle data when modifying items in a stream array. When you modify an item, you are modifying the copy made when you retrieved the item and therefore, you still need to update the data in the container. This is best achieved by means of the AtPut method.
Using DoneItem is just a matter of calling it when you no longer need an item. As an example, look at the DisplayWeatherData procedure:
As you can see, the item is retrieved from the array, the information is displayed and finally, when the item is no longer needed, it is disposed of by a call to DoneItem.
Object arrays
Object stream arrays let you store dynamically allocated objects in a stream. When using the standard object stream arrays, you must follow the same usage guidelines as for the standard stream arrays. There is another type of stream array, however, that works very differently to any other array in the library: the stream-object array.
Stream-object arrays work by using the object's Load and Store methods to store and read the data in and from the stream, respectively. To understand the difference between a standard object stream array and a stream-object array, look at the following object:
type
PContact = ^TContact;
TContact = object(TObject)
FirstName,
LastName,
Phone,
Company : PString;
constructor Init(ALastName, AFirstName, APhone,
ACompany : string);
constructor Load(var S : TStream);
procedure Store(var S : TStream);
destructor Done; virtual;
end;
If you store this object in a standard object stream array, everything except the strings (which are stored somewhere else in the heap -- not in the object itself) will be stored in the stream. However, if you store it in a stream object array, the array will call the object's Store method and therefore, store only the strings into the array. When you retrieve the item from the array, a new instance of a TContact object will be allocated, and then its Load method will be called to retrieve the object's strings from the stream.
Stream object arrays are useful when you want to store very complex objects into a stream (for example, with pointers to other objects). However, there are a few restrictions that must be met before using a stream object array:
- Objects must be registered: you must register your object's type for stream access (see your Borland manuals for detailed information about registering objects).
- Objects must have Load and Store methods: since the stream is accessed exclusively through these methods, you must make sure that your object implements these methods.
- If the objects you are storing contain pointers to other data, you must override the IndexOf method if you wish to find items using the item itself (for example, by using the Delete or Free methods).
See the ARRAYS9.PAS file for an example of how to use a stream object array.
